package com.javabasic.algorithm.leetcode;

import cn.hutool.core.collection.CollUtil;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.List;
import java.util.Stack;
import java.util.stream.Stream;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see     [2866. 美丽塔 II - 力扣（LeetCode）](https://leetcode.cn/problems/beautiful-towers-ii/description/?envType=daily-question&envId=2023-12-21)
 * @since Created by work on 2023/12/21 20:08
 */
public class BeautifulTowersII {


    public static Stream<List<Integer>> testData() {
        return Stream.of(
                CollUtil.newArrayList(5,3,4,1,1)
        );
    }

    @ParameterizedTest
    @MethodSource("testData")
    public void testMaximumSumOfHeights(List<Integer> maxHeights) {
        maximumSumOfHeights(maxHeights);
    }


    /**
     * 解法参考：https://leetcode.cn/problems/beautiful-towers-ii/solutions/2575017/yi-qi-zhao-gong-zuo-liang-ge-dan-diao-zh-axbp/?envType=daily-question&envId=2023-12-21
     *
     * 双缀和(前缀和、后缀和)、单调栈
     *
     * @param maxHeights
     * @return
     */
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int len = maxHeights.size();
        Stack<FixValue> fixStack = new Stack<>();

        long[] prefixSum = new long[len];
        long[] suffixSum = new long[len];

        FixValue topValue;
        int tagNum = 0;

        prefixSum[0] = maxHeights.get(0);
        fixStack.add(new FixValue(1, maxHeights.get(0)));
        for (int i = 1; i < len; i++) {
            prefixSum[i] = prefixSum[i-1] + maxHeights.get(i);
            tagNum = 1;
            while (!fixStack.isEmpty()) {
                topValue = fixStack.pop();

                if (topValue.getValue() < maxHeights.get(i)) {
                    fixStack.add(topValue);
                    break;
                }

                prefixSum[i] -= (topValue.getValue() - maxHeights.get(i)) * topValue.getShowNum();
                tagNum += topValue.getShowNum();
            }
            fixStack.add(new FixValue(tagNum, maxHeights.get(i)));
        }


        fixStack.clear();

        suffixSum[len-1] = maxHeights.get(len-1);
        fixStack.add(new FixValue(1, maxHeights.get(len-1)));
        for (int i = len-2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i+1] + maxHeights.get(i);
            tagNum = 1;
            while (!fixStack.isEmpty()) {
                topValue = fixStack.pop();

                if (topValue.getValue() < maxHeights.get(i)) {
                    fixStack.add(topValue);
                    break;
                }

                suffixSum[i] -= (topValue.getValue() - maxHeights.get(i)) * topValue.getShowNum();
                tagNum += topValue.getShowNum();
            }
            fixStack.add(new FixValue(tagNum, maxHeights.get(i)));
        }

        long result = maxHeights.get(0);
        for (int i = 0; i < len; i++) {
            if (result < prefixSum[i] + suffixSum[i] - maxHeights.get(i)) {
                result = prefixSum[i] + suffixSum[i] - maxHeights.get(i);
            }
        }
        return result;
    }


    /**
     * TTL
     * @param maxHeights
     * @return
     */
    public long maximumSumOfHeights2(List<Integer> maxHeights) {

        int len = maxHeights.size();
        long[] prefixSum = new long[len];
        long[] suffixSum = new long[len];

        long[] prefixOrSuffixArr = new long[len];

        // 计算前缀和
        prefixSum[0] = prefixOrSuffixArr[0] = maxHeights.get(0);

        int tagIndex;
        for (int i = 1; i < len; i++) {
            prefixSum[i] = prefixSum[i-1] + maxHeights.get(i);
            tagIndex = i-1;
            while (tagIndex >= 0) {
                if (prefixOrSuffixArr[tagIndex] > maxHeights.get(i)) {
                    prefixSum[i] -= prefixOrSuffixArr[tagIndex] - maxHeights.get(i);
                    prefixOrSuffixArr[tagIndex] = maxHeights.get(i);
                } else {
                    break;
                }
                tagIndex --;
            }
            prefixOrSuffixArr[i] = maxHeights.get(i);
        }


        // 计算后缀和
        suffixSum[len-1] = prefixOrSuffixArr[len-1] = maxHeights.get(len-1);
        for (int i = len-2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i+1] + maxHeights.get(i);
            tagIndex = i+1;
            while (tagIndex < len) {
                if (prefixOrSuffixArr[tagIndex] > maxHeights.get(i)) {
                    suffixSum[i] -= prefixOrSuffixArr[tagIndex] - maxHeights.get(i);
                    prefixOrSuffixArr[tagIndex] = maxHeights.get(i);
                } else {
                    break;
                }
                tagIndex ++;
            }
            prefixOrSuffixArr[i] = maxHeights.get(i);
        }


        long result = maxHeights.get(0);
        for (int i = 0; i < len; i++) {
            if (result < prefixSum[i] + suffixSum[i] - maxHeights.get(i)) {
                result = prefixSum[i] + suffixSum[i] - maxHeights.get(i);
            }
        }
        return result;
    }
}

class FixValue {
    private long showNum;
    private long value;

    public FixValue(int showNum, int value) {
        this.showNum = showNum;
        this.value = value;
    }

    public long addShow() {
        return  ++this.showNum;
    }

    public long getShowNum() {
        return showNum;
    }

    public void setShowNum(long showNum) {
        this.showNum = showNum;
    }

    public long getValue() {
        return value;
    }

    public void setValue(long value) {
        this.value = value;
    }
}